package club.xiaojiawei.dp;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/1/22 12:49 AM
 * @question 62. 不同路径
 * @description 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * 问总共有多少条不同的路径？
 */
public class UniquePaths62 {

    public static void main(String[] args) {
        UniquePaths62 test = new UniquePaths62();
        int result = test.uniquePaths(3, 7);
        System.out.printf("共有%s种不同路径", result);
    }

    /**
     * dp
     * 时间复杂度O(mn)
     * 空间复杂度O(mn)
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[][] table = new int[m][n];
        for (int i = 0; i < n; i++) {
            table[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            table[i][0] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                table[i][j] = table[i - 1][j] + table[i][j - 1];
            }
        }
        return table[m - 1][n - 1];
    }

    /**
     * 官方-组合数学（nb）
     * 在这m + n - 2 步中，一定有 m - 1 步是要向下走的，不用管什么时候向下走。
     * 那么有几种走法呢？ 可以转化为，给你m + n - 2个不同的数，随便取m - 1个数，有几种取法。
     * 那么这就是一个组合问题了。
     * 时间复杂度O(m)
     * 空间复杂度O(1)
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths2(int m, int n) {
        long ans = 1;
//        求组合的时候，要防止两个int相乘溢出！ 所以不能把算式的分子都算出来，分母都算出来再做除法。
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }

}
